home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
EDUCATE
/
TIERATXT.ARJ
/
TIERRA2.DOC
< prev
Wrap
Text File
|
1991-11-05
|
53KB
|
1,020 lines
O /
================================= x -------------------------------------
o \
\LP
\bf 3.3 ECOLOGY\rm
\eLP
The only communities whose ecology has been explored in detail are those
that operate under selection for small sizes. These communities generally
include a large number of parasites, which do not have functional copy
procedures, and which execute the copy procedures of other creatures within
the search limit. In exploring ecological interactions, the mutation rate
is set at zero, which effectively throws the simulation into ecological time
by stopping evolution. When parasites are present, it is also necessary
to stipulate that creatures must breed true, since parasites have a tendency
to scramble genomes, leading to evolution in the absence of mutation.
0045aaa is a ``metabolic parasite''. Its genome does not include the
copy procedure, however it executes the copy procedure code of
a normal host, such as the ancestor. In an environment favoring small
creatures, 0045aaa has a competitive advantage over the ancestor, however, the
relationship is density dependent. When the hosts become scarce, most of
the parasites are not within the search limit of a copy procedure, and are
not able to reproduce. Their calls to the copy procedure fail and generate
errors, causing them to rise to the top of the reaper queue and die.
When the parasites die off, the host population rebounds. Hosts and parasites
cultured together demonstrate Lotka-Volterra population cycling (Lotka [25];
Volterra [35]; Wilson \& Bossert [36]).
A number of experiments have been conducted to explore the factors affecting
diversity of size classes in these communities. Competitive exclusion trials
were conducted with a series of self-replicating (non-parasitic) genotypes
of different size classes. The experimental soups were initially inoculated
with one individual of each size. A genotype of size 79 was tested against a
genotype of size 80, and then against successively larger size classes. The
interactions were observed by plotting the population of the size 79 class
on the $x$ axis, and the population of the other size class on the $y$ axis.
Sizes 79 and 80 were found to be competitively matched such that neither was
eliminated from the soup. They quickly entered a stable cycle, which exactly
repeated a small orbit. The same general pattern was found in the interaction
between sizes 79 and 81.
When size 79 was tested against size 82, they initially entered a stable
cycle, but after about 4 million instructions they shook out of stability
and the trajectory became chaotic with an attractor that was symmetric about
the diagonal (neither size showed any advantage). This pattern was repeated
for the next several size classes, until size 90, where a marked asymmetry of
the chaotic attractor was evident, favoring size 79. The run of size 79
against size 93 showed a brief stable period of about a million instructions,
which then moved to a chaotic phase without an attractor, which spiraled
slowly down until size 93 became extinct, after an elapsed time of about 6
million instructions.
An interesting exception to this pattern was the interaction between size 79
and size 89. Size 89 is considered to be a ``metabolic cripple'', because
although it is capable of self-replicating, it executes about 40\% more
instructions than normal to replicate. It was eliminated in competition
with size 79, with no loops in the trajectory, after an elapsed time of
under one million instructions.
In an experiment to determine the effects of the presence of parasites on
community diversity, a community consisting of twenty size classes of hosts
was created and allowed to run for 30 million instructions, at which time only
the eight smallest size classes remained. The same community was then
regenerated, but a single genotype (0045aaa) of parasite was also introduced.
After 30 million instructions, 16 size classes remained, including the
parasite. This seems to be an example of a ``keystone'' parasite effect
(Paine [28]).
Symbiotic relationships are also possible. The ancestor was manually dissected
into two creatures, one of size 46 which contained only the code for
self-examination and the copy loop, and one of size 64 which contained only
the code for self-examination and the copy procedure (Figure 3). Neither
could replicate when cultured alone, but when cultured together, they both
replicated, forming a stable mutualistic relationship. It is not known if
such relationships have evolved spontaneously.
\LP
\bf 3.4 EVOLUTIONARY OPTIMIZATION\rm
\eLP
In order to compare the process of evolution between runs of the simulator,
a simple objective quantitative measure of evolution is needed. One such
measure is the degree to which creatures improve their efficiency through
evolution. This provides not only an objective measure of progress in
evolution, but also sheds light on the potential application of synthetic
life systems to the problem of the optimization of machine code.
The efficiency of the creature can be indexed in two ways: the size of the
genome, and the number of CPU cycles needed to execute one replication.
Clearly, smaller genomes can be replicated with less CPU time, however,
during evolution, creatures also decrease the ratio of instructions executed
in one replication, to genome size. The number of instructions executed per
instruction copied, drops substantially.
Figure 4 shows the changes in genome size over a time period of 500 million
instructions executed by the system, for eight sets of mutation rates
differing by factors of two. Mutation rates are measured in terms of 1 in
N individuals being affected by a mutation in each generation. At the highest
two sets of rates tested, one and two, either each (one) or one-half (two)
of the individuals are hit by mutation in each generation. At these rates
the system is unstable. The genomes melt under the heat of the high mutation
rates. The community often dies out, although some runs survived the 500
million instruction runs used in this study. The next lower rate, four,
yields the highest rate of optimization without the risk of death of the
community. At the five lower mutation rates, 8, 16, 32, 64 and 128,
we see successively lower rates of optimization.
Additional replicates were made of the runs at the mutation rate of four
(Fig.\ 5). The replicates differ only in the seed of the
random number generator, all other parameters being identical. These runs
vary in some details such as whether progress is continuous and gradual, or
comes in bursts. Also, each run decreases to a size limit which it can not
proceed past even if it is allowed to run much longer. However, different
runs reach different plateaus of efficiency. The smallest limiting genome
size seen has been 22 instructions, while other runs reached limits of 27
and 30 instructions. Evidently, the system can reach a local optima from
which it can not easily evolve to the global optima.
The increase in efficiency of the replicating algorithms is even greater than
the decrease in the size of the code. The ancestor is 80 instructions
long and requires 839 CPU cycles to replicate. The creature of size 22
only requires 146 CPU cycles to replicate, a 5.75--fold difference in
efficiency. The algorithm of one of these creatures is listed in Appendix D.
Although optimization of the algorithm is maximized at the highest mutation
rate that does not cause instability, ecological interactions appear to be
richer at slightly lower mutation rates. At the rates of eight or 16, we
find the diversity of coexisting size classes to be the greatest, and to
persist the longest. The smaller size classes tend to be various forms of
parasites, thus a diversity of size classes indicates a rich ecology.
An example of even greater optimization is illustrated in Appendix E and
discussed above in section 3.1.1.8. Unrolling of the loop results in a
loop which uses 18 CPU cycles to copy three instructions, or six CPU
cycles executed per instruction copied, compared to 10 for the ancestor.
The creature of size 22 also uses six CPU cycles per instruction copied.
However, the creature of Appendix E uses three extra CPU cycles per loop
to compensate for a separate adaptation that allows it to double its share
of CPU time from the global pool (in essence meaning that relatively speaking,
it uses only three CPU cycles per instruction copied). Without this
compensation it would use only five CPU cycles per instruction copied.
\LP
\rule[6pt]{6.5in}{1pt}
\large \bf 4 SUMMARY\rm \normalsize
\eLP
\LP
\bf 4.1 GENERAL BEHAVIOR OF THE SYSTEM\rm
\eLP
Once the soup is full of replicating creatures, individuals are initially
short lived, generally reproducing only once before dying, thus individuals
turn over very rapidly. More slowly, there appear new genotypes of size 80,
and then new size classes. There are changes in the genetic composition
of each size class, as new mutants appear, some of which increase significantly
in frequency, eventually replacing the original genotype. The size classes
which dominate the community also change through time, as new size classes
appear, some of which competitively exclude sizes present earlier.
Once the community becomes diverse, there is a greater variance in
the longevity and fecundity of individuals.
In addition to an increase in the raw diversity of genotypes and genome sizes,
there is an increase in the ecological diversity. Obligate commensal
parasites evolve, which are not capable of self-replication in isolated
culture, but which can replicate when cultured with normal (self-replicating)
creatures. These parasites execute some parts of the code of their hosts,
but cause them no direct harm, except as competitors. Some potential hosts
have evolved immunity to the parasites, and some parasites have evolved to
circumvent this immunity.
In addition, facultative hyper-parasites have evolved, which can
self-replicate in isolated culture, but when subjected to parasitism, subvert
the parasites energy metabolism to augment their own reproduction.
Hyper-parasites drive parasites to extinction, resulting in complete
domination of the communities. The relatively high degrees of genetic
relatedness within the hyper-parasite dominated communities leads to the
evolution of sociality in the sense of creatures that can only replicate
when they occur in aggregations. These social aggregations are then invaded
by hyper-hyper-parasite cheaters.
Mutations and the ensuing replication errors lead to an increasing diversity
of sizes and genotypes of self-replicating creatures in the soup. Within
the first 100 million instructions of elapsed time, the soup evolves to
a state in which about a dozen more-or-less persistent size classes coexist.
The relative abundances and specific list of the size classes varies over time.
Each size class consists of a number of distinct genotypes which also vary
over time.
The rate of evolution increases with the mutation rate until the system
becomes unstable, and the community dies at rates above one mutation per four
generations. Ecological interactions are richer and more sustained at
slightly lower rates, one mutation per eight or 16 generations. At mutation
rates of one per four generations, under selection for small sizes, creatures
will optimize to a genome size in the 22 to 30 instruction size range within
as little as 300 million instructions of elapsed time. Each of these runs
will reach a local optima which it evidently cannot escape from, although it
may not be the global optima.
\LP
\bf 4.2 INCREASING COMPLEXITY\rm
\eLP
The unrolled loop (section 3.1.1.8) is an example of the ability of evolution
to produce an increase in complexity, gradually over a long period of time.
The interesting thing about the loop unrolling optimization technique is that
it requires more complex code. The resulting creature has a genome size of 36,
compared to its ancestor of size 80, yet it has packed a much more complex
algorithm into less than half the space (Appendix E).
This is a classic example of intricate design in evolution. One wonders how
it could have arisen through random bit flips, as every component of the code
must be in place in order for the algorithm to function. Yet the code
includes a classic mix of apparent intelligent design, and the chaotic hand
of evolution. The optimization technique is a very clever one invented by
humans, yet it is implemented in a mixed up but functional style that no human
would use (unless perhaps very intoxicated).
\LP
\bf 4.3 EMERGENCE\rm
\eLP
The ``physical'' environment presented by the simulator is quite simple,
consisting of the energy resource (CPU time) doled out rather uniformly by
the time slicer, and memory space which is completely uniform and always
available. In light of the nature of the physical environment, the implicit
fitness function would presumably favor the evolution of creatures which are
able to replicate with less CPU time, and this does in fact occur. However,
much of the evolution in the system consists of the creatures discovering ways
to exploit one-another. The creatures invent their own fitness functions
through adaptation to their biotic (``living'') environment. These ecological
interactions are not programmed into the system, but emerge spontaneously as
the creatures discover each other and invent their own games.
In the Tierran world, creatures which initially
do not interact, discover means to exploit one another, and in response, means
to avoid exploitation. The original fitness landscape of the ancestor
consists only of the efficiency parameters of the replication algorithm, in
the context of the properties of the reaper and slicer queues. When by
chance, genotypes appear that exploit other creatures, selection acts to
perfect the mechanisms of exploitation, and mechanisms of defense to that
exploitation. The original fitness landscape was based only on adaptations
of the organism to its physical environment. The
new fitness landscape retains those features, but adds to it adaptations to
the biotic environment, the other creatures. Because the fitness landscape
includes an ever increasing realm of adaptations to other creatures which
are themselves evolving, it can facilitate an auto-catalytic increase in
complexity and diversity of organisms.
Evolutionary theory suggests that adaptation to the biotic environment (other
organisms) rather than to the physical environment is the primary force
driving the auto-catalytic diversification of organisms (Stanley [34]). It
is encouraging to discover that the process has already begun in the Tierran
world. It is worth noting that the results presented here are based on
evolution of the first creature that I designed, written in the first
instruction set that I designed. Comparison to the creatures that have
evolved shows that the one I designed is not a particularly clever one. Also,
the instruction set that the creatures are based on is certainly not very
powerful (apart from those special features incorporated to enhance its
evolvability). It would appear then that it is rather easy to create life.
Evidently, virtual life is out there, waiting for us to provide environments
in which it may evolve.
\LP
\bf 4.4 SYNTHETIC BIOLOGY\rm
\eLP
One of the most uncanny of evolutionary phenomena is the ecological convergence
of biota living on different continents or in different epochs. When a
lineage of organisms undergoes an adaptive radiation (diversification),
it leads to an array of relatively stable ecological forms. The specific
ecological forms are often recognizable from lineage to lineage. For example
among dinosaurs, the \it Pterosaur\rm, \it Triceratops\rm,
\it Tyrannosaurus \rm and \it Ichthyosaur \rm
are ecological parallels respectively, to the bat, rhinoceros, lion and
porpoise of modern mammals. Similarly, among modern placental mammals, the
gray wolf, flying squirrel, great anteater and common mole are ecological
parallels respectively, to the Tasmanian wolf, honey glider, banded anteater
and marsupial mole of the marsupial mammals of Australia.
Given these evidently powerful convergent forces, it should perhaps not be
surprising that as adaptive radiations proceed among digital organisms, we
encounter recognizable ecological forms, in spite of the fundamentally
distinct physics and chemistry on which they are based. Ideally, comparisons
should be made among organisms of comparable complexity. It may not be
appropriate to compare viruses to mammals. Unfortunately, the organic
creatures most comparable to digital organisms, the RNA creatures, are no
longer with us. Since digital organisms are being compared to modern organic
creatures of much greater complexity, ecological comparisons must be made in
the broadest of terms.
Trained biologists will tend to view synthetic life in the same terms that
they have come to know organic life. Having been trained as an ecologist
and evolutionist, I have seen in my synthetic communities, many of the
ecological and evolutionary properties that are well known from natural
communities. Biologists trained in other specialties will likely observe
other familiar properties. It seems that what we see is what we know. It
is likely to take longer before we appreciate the unique properties of these
new life forms.
\LP
\bf 4.5 FUTURE DIRECTIONS\rm
\eLP
For the immediate future, my research will involve three main thrusts:
\bf Computational: \rm The computational issue is how to design a computer
architecutre and operating system that will support the natural evolution
of \it machine code\rm . Von Neumann style machine codes are considered to
be brittle, in the sense that they are not robust to the genetic operations
of mutation and recombination. Any random change in a program is almost
100\% certain to break the program.
The most significant accomplishment of my work to date is finding a way to
overcome this brittleness with only a slight modification of standard machine
codes. However, this success was achieved in the first attempt. Therefore
it is not known what features are essential for evolvability, and I
certainly do not know what is the optimal architecture.
The primary computational objective then is to experiment with a large
number of variations on the successful architecture in order to find the
optimal balance of computational power and evolvability. This work has
begun but needs to be scaled up.
There are however, other important computational goals. We must experiment
with artificial selection on application programs. So far all work has
involved natural selection on ``wild'' algorithms that do no useful work.
I want to develop an analog to genetic engineering, in which application
codes are inserted into the genomes of digital organisms and evolved to
greater optimality or new functionality.
It should be possible to develop cross-assemblers between Tierran architectures
and real assembler languages. Application code written and compiled to run on
real machines could be cross-assembled into the new Tierran languages. Each
procedure could then be inserted into the genome of a creature. Creatures
could be rewarded with CPU time in proportion to the efficacy and efficiency
of the evolving inserted code. In this way, artificial selection would lead
to the optimization of the inserted code, which could then be cross-assembled
back into the real machine code.
If artificial selection of application programs proved to be practical, it
would be worthwhile to render the best Tierran virtual instruction sets in
silicon, thereby greatly accelerating the process. At present, maximum
optimization can be achieved in a few hours of running the Tierran virtual
computer. If a real computer were based on the architectural principals of
the Tierran computer, the speed would be multiplied by about two orders of
magnitude. If the real machine were massively parallel, there could be
additional gains of five to six orders of magnitude. If machine code could
evolve that quickly, then there is the possibility of using it as a generative
process in addition to an optimization procedure. There may also be some
potential application in the areas of machine learning or adaptive programming.
Another long term objective is to use digital organisms evolving freely or
under artificial selection, as a source of new paradigms for the programming
of massively parallel machines. The virtual computer that supports digital
evolution is a parallel machine of the MIMD (multiple instruction multiple
data) type. One of the biggest problems facing computer science today is
the development of techniques of parallel programming. Digital organisms
program themselves, using evolution. They have discovered on their own, known
programming techniques such as unrolling loops. They will discover techniques
that are naturally efficient on parallel machines, and we should be able
to learn from their innovations.
The kinds of ecological interactions already
observed in digital communities could in another light, be viewed as
optimization techniques for parallel programming (e.g., the sharing of
code fragments). However, these interactions evolve in a ``jungle''-like
environment where most interactions are of an adversarial nature. When
evolving large parallel application programs, the most viable model would
be a multi-cellular one, where many cells would cooperate on a common
problem. A multi-cellular model is under development. In the end, evolution
may prove to be the best method of programming massively parallel machines.
\bf Biological: \rm I plan to move the biological model ahead of its
present state. This will primarly involve the incorporation of facilities
to support diploidy, organized sexuality, and multi-cellularity. The
methods for these advances have already been conceptually worked out, and
the implementation has begun. When these improvements are made, the long
term biological goals are to use the model to test ecological and
evolutionary theory, in such areas as: the evolution of sex, selection across
hierarchical levels, and factors affecting diversity of ecological communities.
It is hoped that it will be possible to engineer the system up to a condition
analagous to the threshold of the Cambrian explosion of diversity, and then
just allow the complexity and diversity of the digital system to explode
spontaneously.
\bf Educational: \rm I wish to distribute both source and executables
for use as an educational and research tool. However, some
additional work is needed to make the program fully portable and to provide
a user friendly graphic user interface. This work is underway at a slow
pace.
\LP
\rule[6pt]{6.5in}{1pt}
\large \bf 5 ACKNOWLEDGMENT\rm \normalsize
\eLP
I thank Marc Cygnus, Robert Eisenberg, Doyne Farmer, Walter Fontana,
Stephanie Forrest, Chris Langton, Dan Pirone, Stephen Pope, and
Steen Rasmussen, for their discussions or readings of the manuscripts.
I thank the Santa Fe Institute for their support.
Contribution No.\ XXX from the Ecology Program, School
of Life and Health Sciences, University of Delaware.
\newpage
\LP
\rule[6pt]{6.5in}{1pt}
\large \bf 6 REFERENCES\rm \normalsize
\eLP
\XP
[1] Ackley, D. H. \& Littman, M. S. ``Learning from natural
selection in an artificial environment.'' In: \it Proceedings of the
International Joint Conference on Neural Networks, Volume I, Theory Track,
Neural and Cognitive Sciences Track\rm , IJCNN Winter 1990, Washington, DC.
Hillsdale, New Jersey: Lawrence Erlbaum Associates, 1990.
[2] Aho, A. V., Hopcroft, J. E. \& Ullman, J. D. \it The design and
analysis of computer algorithms\rm . Reading, Mass.: Addison-Wesley Publ.\
Co, 1974.
[3] Bagley, R. J., Farmer, J. D., Kauffman, S. A., Packard, N. H., Perelson,
A. S. \& Stadnyk, I. M. ``Modeling adaptive biological systems.'' Unpublished
paper, 1989.
[4] Barbieri, M. \it The semantic theory of evolution\rm . London:
Harwood Academic Publishers, 1985.
[5] Cariani, P. ``Emergence and artificial life.'' In: \it Artificial
Life II\rm, edited by C. Langton, D. Farmer and S. Rasmussen.
Redwood City, CA: Addison-Wesley, 1991, 000--000.
[6] Cohen, F. \it Computer viruses: theory and experiments\rm .
Ph.\ D. dissertation, U. of Southern California, 1984.
[7] Dawkins, R. \it The blind watchmaker\rm . New York: W. W. Norton
\& Co., 1987.
[8] Dawkins, R. ``The evolution of evolvability.'' In: \it Artificial life:
proceedings of an interdisciplinary workshop on the synthesis and simulation
of living systems\rm , edited by C. Langton. Redwood City, CA:
Addison-Wesley, 1989, 201--220.
[9] Denning, P. J. ``Computer viruses.'' \it Amer.\ Sci.\ \bf 76 \rm
(1988): 236--238.
[10] Dewdney, A. K. ``Computer recreations: In the game called Core
War hostile programs engage in a battle of bits.'' \it Sci.\ Amer.\ \bf
250 \rm (1984): 14--22.
[11] Dewdney, A. K. ``Computer recreations: A core war bestiary of
viruses, worms and other threats to computer memories.'' \it Sci.\ Amer.\ \bf
252 \rm (1985a): 14--23.
[12] Dewdney, A. K. ``Computer recreations: Exploring the field of
genetic algorithms in a primordial computer sea full of flibs.''
\it Sci.\ Amer.\ \bf 253 \rm (1985b): 21--32.
[13] Dewdney, A. K. ``Computer recreations: A program called MICE
nibbles its way to victory at the first core war tournament.'' \it Sci.\
Amer.\ \bf 256 \rm (1987): 14--20.
[14] Dewdney, A. K. ``Of worms, viruses and core war.''
\it Sci.\ Amer.\ \bf 260 \rm (1989): 110--113.
[15] Eldredge, N. \& Gould, S. J. ``Punctuated equilibria: an alternative
to phyletic gradualism.'' In: \it Models in Paleobiology\rm , edited by
J. M. Schopf. San Francisco: Greeman, Cooper, 1972, 82--115.
[16] Farmer, J. D., Kauffman, S. A., \& Packard, N. H. ``Autocatalytic
replication of polymers.'' \it Physica D \bf 22 \rm (1986): 50--67.
[17] Farmer, J. D. \& Belin, A. ``Artificial life: the
coming evolution.'' Proceedings in celebration of Murray Gell-Man's 60th
Birthday. Cambridge: University Press. In press.
[18] Gould, S. J. \it Wonderful life, the Burgess shale and the nature
of history\rm . New York: W. W. Norton \& Company, 1989.
[19] Gould, S. J. \& Eldredge, N. ``Punctuated equilibria: the tempo and
mode of evolution reconsidered.'' \it Paleobiology \bf 3 \rm (1977): 115--151.
[20] Holland, J. H. \it Adaptation in natural and artificial systems:
an introductory analysis with applications to biology, control, and
artificial intelligence\rm . Ann Arbor: Univ.\ of Michigan Press, 1975.
[21] Holland, J. H. ``Studies of the spontaneous emergence of
self-replicating systems using cellular automata and formal grammars.''
In: \it Automata, Languages, Development\rm , edited by Lindenmayer, A.,
\& Rozenberg, G. New York: North-Holland, 1976, 385--404.
[22] Langton, C. G. ``Studying artificial life with cellular automata.''
\it Physica \bf 22D \rm (1986): 120--149.
[23] Langton, C. G. ``Virtual state machines in cellular automata.''
\it Complex Systems \bf 1 \rm (1987): 257--271.
[24] Langton, C. G. ``Artificial life.'' In: \it Artificial life: proceedings
of an interdisciplinary workshop on the synthesis and simulation of living
systems\rm , edited by Langton, C. Vol. 6 in the series: Santa Fe Institute
studies in the sciences of complexity. Redwood City, CA: Addison-Wesley,
1989, 1--47.
[25] Lotka, A. J. \it Elements of physical biology\rm . Baltimore: Williams
and Wilkins, 1925, reprinted as \it Elements of mathematical biology\rm ,
Dover Press, 1956.
[26] Minsky, M. L. \it Computation: finite and infinite machines\rm .
Englewood Cliffs, N.J.: Prentice-Hall, 1976.
[27] Morris, S. C. ``Burgess shale faunas and the cambrian explosion.''
\it Science \bf 246 \rm (1989): 339--346.
[28] Paine, R. T. ``Food web complexity and species diversity.''
\it Am.\ Nat.\ \bf 100 \rm (1966): 65--75.
[29] Packard, N. H. ``Intrinsic adaptation in a simple model for
evolution.'' In: \it Artificial life: proceedings of an interdisciplinary
workshop on the synthesis and simulation of living systems\rm , edited by C.
Langton. Redwood City, CA: Addison-Wesley, 1989, 141--155.
[30] Pattee, H. H. ``Simulations, realizations, and theories of life.''
In: \it Artificial life: proceedings of an interdisciplinary workshop on
the synthesis and simulation of living systems\rm , edited by C. Langton.
Redwood City, CA: Addison-Wesley, 1989, 63--77.
[31] Rasmussen, S., Knudsen, C., Feldberg, R. \& Hindsholm, M. ``The
coreworld: emergence and evolution of cooperative structures in a
computational chemistry'' \it Physica D \bf 42 \rm (1990): 111--134.
[32] Rheingold, H. (1988). Computer viruses. \it Whole Earth Review \bf
Fall \rm (1988): 106.
[33] Spafford, E. H., Heaphy, K. A. \& Ferbrache, D. J. \it Computer
viruses, dealing with electronic vandalism and programmed threats\rm .
ADAPSO, 1300 N. 17th Street, Suite 300, Arlington, VA 22209, 1989.
[34] Stanley, S. M. ``An ecological theory for the sudden origin
of multicellular life in the late precambrian.'' \it Proc.\ Nat.\ Acad.\
Sci.\ \bf 70 \rm (1973): 1486--1489.
[35] Volterra, V. ``Variations and fluctuations of the number of individuals
in animal species living together.'' In: \it Animal Ecology\rm , edited by
R. N. Chapman. New York: McGraw-Hill, 1926, 409--448.
[36] Wilson, E. O. \& Bossert, W. H. \it A primer of population
biology\rm . Stamford, Conn: Sinauer Associates, 1971.
\eXP
\newpage
% \addtocounter{page}{1}
\LP
\bf Figure 1. Metabolic flow chart for the ancestor, parasite, hyper-parasite,
and their interactions: \rm ax, bx and cx refer to CPU registers where location
and size information are stored. [ax] and [bx] refer to locations in the
soup indicated by the values in the ax and bx registers. Patterns such as
1101 are complementary templates used for addressing. Arrows outside of boxes
indicate jumps in the flow of execution of the programs. The dotted-line
arrows indicate flow of execution between creatures. The parasite lacks the
copy procedure, however, if it is within the search limit of the copy
procedure of a host, it can locate, call and execute that procedure, thereby
obtaining the information needed to complete its replication. The host is
not adversely affected by this informational parasitism, except through
competition with the parasite, which is a superior competitor. Note that
the parasite calls the copy procedure of its host with the expectation that
control will return to the parasite when the copy procedure returns. However,
the hyper-parasite jumps out of the copy procedure rather than returning,
thereby seizing control from the parasite. It then proceeds to reset the CPU
registers of the parasite with the location and size of the hyper-parasite,
causing the parasite to replicate the hyper-parasite genome thereafter.
\newpage
\addtocounter{page}{1}
\bf Figure 2. Metabolic flow chart for social hyper-parasites, their
associated hyper-hyper-parasite cheaters, and their interactions. \rm Symbols
are as described for Fig.\ 1. Horizontal dashed lines indicate the boundaries
between individual creatures. On both the left and right, above the dashed
line at the top of the figure is the lowermost fragment of a
social-hyper-parasite. Note (on the left) that neighboring social
hyper-parasites cooperate in returning the flow of execution to the beginning
of the creature for self-re-examination. Execution jumps back to the end of
the creature above, but then falls off the end of the creature without
executing any instructions of consequence, and enters the top of the creature
below. On the right, a cheater is inserted between the two
social-hyper-parasites. The cheater captures control of execution when it
passes between the social individuals. It sets the CPU registers with its own
location and size, and then skips over the self-examination step when it
returns control of execution to the social creature below.
\newpage
\addtocounter{page}{1}
\bf Figure 3. Metabolic flow chart for obligate symbionts and their
interactions. \rm Symbols are as described for Fig.\ 1. Neither creature is
able to self-replicate in isolation. However, when cultured together, each
is able to replicate by using information provided by the other.
\newpage
\addtocounter{page}{1}
\bf Figure 4. Evolutionary optimization at eight sets of mutation rates. \rm
In each run, the three mutation rates: move mutations (copy error), flaws
and background mutations (cosmic rays) are set relative to the generation
time. In each case, the background mutation rate is the lowest, affecting
a cell once in twice as many generations as the move mutation rate. The
flaw rate is intermediate, affecting a cell once in 1.5 times as many
generations as the move mutation rate. For example in one run, the move
mutation will affect a cell line on the average once every 4 generations,
the flaw will occur once every 6 generations, and the background mutation
once every 8 generations. The horizontal axis shows elapsed time in
hundreds of millions of instructions executed by the system. The vertical
axis shows genome size in instructions. Each point indicates the first
appearance of a new genotype which crossed the abundance thresholds of
either 2\% of the population of cells in the soup, or occupation of 2\% of
the memory. The number of generations per move mutation is indicated by
a number in the upper right hand corner of each graph.
\newpage
\addtocounter{page}{3}
\bf Figure 5. Variation in evolutionary optimization under constant
conditions. \rm Based on a mutation rate of four generations per move
mutation, all other parameters as in Fig.\ 4. The plots are otherwise
as described for Fig.\ 4.
\newpage
\addtocounter{page}{1}
Table 1: Genebank. Table of numbers of size classes in the genebank. Left
column is size class, right column is number of self-replicating genotypes
of that size class. 305 sizes, 29,275 genotypes.
\eLP
\begin{verbatim}
0034 1 0092 362 0150 2 0205 5 0418 1 5213 2
0041 2 0093 261 0151 1 0207 3 0442 10 5229 4
0043 12 0094 241 0152 2 0208 2 0443 1 5254 1
0044 7 0095 211 0153 1 0209 1 0444 61 5888 36
0045 191 0096 232 0154 2 0210 9 0445 1 5988 1
0046 7 0097 173 0155 3 0211 4 0456 2 6006 2
0047 5 0098 92 0156 77 0212 4 0465 6 6014 1
0048 4 0099 117 0157 270 0213 5 0472 6 6330 1
0049 8 0100 77 0158 938 0214 47 0483 1 6529 1
0050 13 0101 62 0159 836 0218 1 0484 8 6640 1
0051 2 0102 62 0160 3229 0219 1 0485 3 6901 5
0052 11 0103 27 0161 1417 0220 2 0486 9 6971 1
0053 4 0104 25 0162 174 0223 3 0487 2 7158 2
0054 2 0105 28 0163 187 0226 2 0493 2 7293 3
0055 2 0106 19 0164 46 0227 7 0511 2 7331 1
0056 4 0107 3 0165 183 0231 1 0513 1 7422 70
0057 1 0108 8 0166 81 0232 1 0519 1 7458 1
0058 8 0109 2 0167 71 0236 1 0522 6 7460 7
0059 8 0110 8 0168 9 0238 1 0553 1 7488 1
0060 3 0111 71 0169 15 0240 3 0568 6 7598 1
0061 1 0112 19 0170 99 0241 1 0578 1 7627 63
0062 2 0113 10 0171 40 0242 1 0581 3 7695 1
0063 2 0114 3 0172 44 0250 1 0582 1 7733 1
0064 1 0115 3 0173 34 0251 1 0600 1 7768 2
0065 4 0116 5 0174 15 0260 2 0683 1 7860 25
0066 1 0117 3 0175 22 0261 1 0689 1 7912 1
0067 1 0118 1 0176 137 0265 2 0757 6 8082 3
0068 2 0119 3 0177 13 0268 1 0804 2 8340 1
0069 1 0120 2 0178 3 0269 1 0813 1 8366 1
0070 7 0121 60 0179 1 0284 16 0881 6 8405 5
0071 5 0122 9 0180 16 0306 1 0888 1 8406 2
0072 17 0123 3 0181 5 0312 1 0940 2 8649 2
0073 2 0124 11 0182 27 0314 1 1006 6 8750 1
0074 80 0125 6 0184 3 0316 2 1016 1 8951 1
0075 56 0126 11 0185 21 0318 3 1077 5 8978 3
0076 21 0127 1 0186 9 0319 2 1116 1 9011 3
0077 28 0130 3 0187 3 0320 23 1186 1 9507 3
0078 409 0131 2 0188 11 0321 5 1294 7 9564 3
0079 850 0132 5 0190 20 0322 21 1322 7 9612 1
0080 7399 0133 2 0192 12 0330 1 1335 1 9968 1
0081 590 0134 7 0193 4 0342 5 1365 11 10259 31
0082 384 0135 1 0194 4 0343 1 1631 1 10676 1
0083 886 0136 1 0195 11 0351 1 1645 3 11366 5
0084 1672 0137 1 0196 19 0352 3 2266 1 11900 1
0085 1531 0138 1 0197 2 0386 1 2615 2 12212 2
0086 901 0139 2 0198 3 0388 2 2617 9 15717 3
0087 944 0141 6 0199 35 0401 3 2671 7 16355 1
0088 517 0143 1 0200 1 0407 1 3069 3 17356 3
0089 449 0144 4 0201 84 0411 22 4241 1 18532 1
0090 543 0146 1 0203 1 0412 3 5101 15 23134 14
0091 354 0149 1 0204 1 0416 1 5157 9
\end{verbatim}
\newpage
\baselineskip = 14pt
\LP
\bf APPENDIX A\rm
\eLP
Structure definition to implement the Tierra virtual CPU.
The complete source code for the Tierra Simulator can be obtained by
contacting the author by email.
\begin{verbatim}
struct cpu { /* structure for registers of virtual cpu */
int ax; /* address register */
int bx; /* address register */
int cx; /* numerical register */
int dx; /* numerical register */
char fl; /* flag */
char sp; /* stack pointer */
int st[10]; /* stack */
int ip; /* instruction pointer */
} ;
\end{verbatim}
\LP
\bf APPENDIX B\rm
\eLP
Abbreviated code for implementing the CPU cycle of the Tierra Simulator.
\begin{verbatim}
void main(void)
{ get_soup();
life();
write_soup();
}
void life(void) /* doles out time slices and death */
{ while(inst_exec_c < alive) /* control the length of the run */
{ time_slice(this_slice); /* this_slice is current cell in queue */
incr_slice_queue(); /* increment this_slice to next cell in queue */
while(free_mem_current < free_mem_prop * soup_size)
reaper(); /* if memory is full to threshold, reap some cells */
}
}
void time_slice(int ci)
{ Pcells ce; /* pointer to the array of cell structures */
char i; /* instruction from soup */
int di; /* decoded instruction */
int j, size_slice;
ce = cells + ci;
for(j = 0; j < size_slice; j++)
{ i = fetch(ce->c.ip); /* fetch instruction from soup, at address ip */
di = decode(i); /* decode the fetched instruction */
execute(di, ci); /* execute the decoded instruction */
increment_ip(di,ce); /* move instruction pointer to next instruction */
system_work(); /* opportunity to extract information */
}
}
void execute(int di, int ci)
{ switch(di)
{ case 0x00: nop_0(ci); break; /* no operation */
case 0x01: nop_1(ci); break; /* no operation */
case 0x02: or1(ci); break; /* flip low order bit of cx, cx ^= 1 */
case 0x03: shl(ci); break; /* shift left cx register, cx <<= 1 */
case 0x04: zero(ci); break; /* set cx register to zero, cx = 0 */
case 0x05: if_cz(ci); break; /* if cx==0 execute next instruction */
case 0x06: sub_ab(ci); break; /* subtract bx from ax, cx = ax - bx */
case 0x07: sub_ac(ci); break; /* subtract cx from ax, ax = ax - cx */
case 0x08: inc_a(ci); break; /* increment ax, ax = ax + 1 */
case 0x09: inc_b(ci); break; /* increment bx, bx = bx + 1 */
case 0x0a: dec_c(ci); break; /* decrement cx, cx = cx - 1 */
case 0x0b: inc_c(ci); break; /* increment cx, cx = cx + 1 */
case 0x0c: push_ax(ci); break; /* push ax on stack */
case 0x0d: push_bx(ci); break; /* push bx on stack */
case 0x0e: push_cx(ci); break; /* push cx on stack */
case 0x0f: push_dx(ci); break; /* push dx on stack */
case 0x10: pop_ax(ci); break; /* pop top of stack into ax */
case 0x11: pop_bx(ci); break; /* pop top of stack into bx */
case 0x12: pop_cx(ci); break; /* pop top of stack into cx */
case 0x13: pop_dx(ci); break; /* pop top of stack into dx */
case 0x14: jmp(ci); break; /* move ip to template */
case 0x15: jmpb(ci); break; /* move ip backward to template */
case 0x16: call(ci); break; /* call a procedure */
case 0x17: ret(ci); break; /* return from a procedure */
case 0x18: mov_cd(ci); break; /* move cx to dx, dx = cx */
case 0x19: mov_ab(ci); break; /* move ax to bx, bx = ax */
case 0x1a: mov_iab(ci); break; /* move instruction at address in bx
to address in ax */
case 0x1b: adr(ci); break; /* address of nearest template to ax */
case 0x1c: adrb(ci); break; /* search backward for template */
case 0x1d: adrf(ci); break; /* search forward for template */
case 0x1e: mal(ci); break; /* allocate memory for daughter cell */
case 0x1f: divide(ci); break; /* cell division */
}
inst_exec_c++;
}
\end{verbatim}
\newpage
\LP
\bf APPENDIX C\rm
\eLP
Assembler source code for the ancestral creature.
\begin{verbatim}
genotype: 80 aaa origin: 1-1-1990 00:00:00:00 ancestor
parent genotype: human
1st_daughter: flags: 0 inst: 839 mov_daught: 80
2nd_daughter: flags: 0 inst: 813 mov_daught: 80
nop_1 ; 01 0 beginning template
nop_1 ; 01 1 beginning template
nop_1 ; 01 2 beginning template
nop_1 ; 01 3 beginning template
zero ; 04 4 put zero in cx
or1 ; 02 5 put 1 in first bit of cx
shl ; 03 6 shift left cx
shl ; 03 7 shift left cx, now cx = 4
; ax = bx =
; cx = template size dx =
mov_cd ; 18 8 move template size to dx
; ax = bx =
; cx = template size dx = template size
adrb ; 1c 9 get (backward) address of beginning template
nop_0 ; 00 10 compliment to beginning template
nop_0 ; 00 11 compliment to beginning template
nop_0 ; 00 12 compliment to beginning template
nop_0 ; 00 13 compliment to beginning template
; ax = start of mother + 4 bx =
; cx = template size dx = template size
sub_ac ; 07 14 subtract cx from ax
; ax = start of mother bx =
; cx = template size dx = template size
mov_ab ; 19 15 move start address to bx
; ax = start of mother bx = start of mother
; cx = template size dx = template size
adrf ; 1d 16 get (forward) address of end template
nop_0 ; 00 17 compliment to end template
nop_0 ; 00 18 compliment to end template
nop_0 ; 00 19 compliment to end template
nop_1 ; 01 20 compliment to end template
; ax = end of mother bx = start of mother
; cx = template size dx = template size
inc_a ; 08 21 to include dummy statement to separate creatures
sub_ab ; 06 22 subtract start address from end address to get size
; ax = end of mother bx = start of mother
; cx = size of mother dx = template size
nop_1 ; 01 23 reproduction loop template
nop_1 ; 01 24 reproduction loop template
nop_0 ; 00 25 reproduction loop template
nop_1 ; 01 26 reproduction loop template
mal ; 1e 27 allocate memory for daughter cell, address to ax
; ax = start of daughter bx = start of mother
; cx = size of mother dx = template size
call ; 16 28 call template below (copy procedure)
nop_0 ; 00 29 copy procedure compliment
nop_0 ; 00 30 copy procedure compliment
nop_1 ; 01 31 copy procedure compliment
nop_1 ; 01 32 copy procedure compliment
divide ; 1f 33 create independent daughter cell
jmp ; 14 34 jump to template below (reproduction loop, above)
nop_0 ; 00 35 reproduction loop compliment
nop_0 ; 00 36 reproduction loop compliment
nop_1 ; 01 37 reproduction loop compliment
nop_0 ; 00 38 reproduction loop compliment
if_cz ; 05 39 this is a dummy instruction to separate templates
; begin copy procedure
nop_1 ; 01 40 copy procedure template
nop_1 ; 01 41 copy procedure template
nop_0 ; 00 42 copy procedure template
nop_0 ; 00 43 copy procedure template
push_ax ; 0c 44 push ax onto stack
push_bx ; 0d 45 push bx onto stack
push_cx ; 0e 46 push cx onto stack
nop_1 ; 01 47 copy loop template
nop_0 ; 00 48 copy loop template
nop_1 ; 01 49 copy loop template
nop_0 ; 00 50 copy loop template
mov_iab ; 1a 51 move contents of [bx] to [ax]
dec_c ; 0a 52 decrement cx
if_cz ; 05 53 if cx == 0 perform next instruction, otherwise skip it
jmp ; 14 54 jump to template below (copy procedure exit)
nop_0 ; 00 55 copy procedure exit compliment
nop_1 ; 01 56 copy procedure exit compliment
nop_0 ; 00 57 copy procedure exit compliment
nop_0 ; 00 58 copy procedure exit compliment
inc_a ; 08 59 increment ax
inc_b ; 09 60 increment bx
jmp ; 14 61 jump to template below (copy loop)
nop_0 ; 00 62 copy loop compliment
nop_1 ; 01 63 copy loop compliment
nop_0 ; 00 64 copy loop compliment
nop_1 ; 01 65 copy loop compliment
if_cz ; 05 66 this is a dummy instruction, to separate templates
nop_1 ; 01 67 copy procedure exit template
nop_0 ; 00 68 copy procedure exit template
nop_1 ; 01 69 copy procedure exit template
nop_1 ; 01 70 copy procedure exit template
pop_cx ; 12 71 pop cx off stack
pop_bx ; 11 72 pop bx off stack
pop_ax ; 10 73 pop ax off stack
ret ; 17 74 return from copy procedure
nop_1 ; 01 75 end template
nop_1 ; 01 76 end template
nop_1 ; 01 77 end template
nop_0 ; 00 78 end template
if_cz ; 05 79 dummy statement to separate creatures
\end{verbatim}
\newpage
\LP
\bf APPENDIX D\rm
\eLP
Assembler source code for the smallest self-replicating creature.
\begin{verbatim}
genotype: 0022abn parent genotype: 0022aak
1st_daughter: flags: 1 inst: 146 mov_daught: 22 breed_true: 1
2nd_daughter: flags: 0 inst: 142 mov_daught: 22 breed_true: 1
InstExecC: 437 InstExec: 625954 origin: 662865379 Wed Jan 2 20:16:19 1991
MaxPropPop: 0.1231 MaxPropInst: 0.0568
nop_0 ; 00 0
adrb ; 1c 1 find beginning
nop_1 ; 01 2
divide ; 1f 3 fails the first time it is executed
sub_ac ; 07 4
mov_ab ; 19 5
adrf ; 1d 6 find end
nop_0 ; 00 7
inc_a ; 08 8 to include final dummy statement
sub_ab ; 06 9 calculate size
mal ; 1e 10
push_bx ; 0d 11 save beginning address on stack in order to `return' there
nop_0 ; 00 12 top of copy loop
mov_iab ; 1a 13
dec_c ; 0a 14
if_cz ; 05 15
ret ; 17 16 jump to beginning, address saved on stack
inc_a ; 08 17
inc_b ; 09 18
jmpb ; 15 19 bottom of copy loop (6 instructions executed per loop)
nop_1 ; 01 20
mov_iab ; 1a 21 dummy statement to terminate template
\end{verbatim}
\newpage
\LP
\bf APPENDIX E\rm
\eLP
Assembler code for the central copy loop of the ancestor
(80aaa) and decendant after fifteen billion instructions (72etq). Within
the loop, the ancestor does each of the following operations once: copy
instruction (51), decrement cx (52), increment ax (59) and increment bx (60).
The decendant performs each of the following operations three times within
the loop: copy instruction (15, 22, 26), increment ax (20, 24, 31) and
increment bx (21, 25, 32). The decrement cx operation occurs five times
within the loop (16, 17, 19, 23, 27). Instruction 28 flips the low order
bit of the cx register. Whenever this latter instruction is reached, the
value of the low order bit is one, so this amounts to a sixth instance of
decrement cx. This means that there are two decrements for every increment.
The reason for this is related to another adaptation of this creature. When
it calculates its size, it shifts left (12) before allocating space for the
daughter (13). This has the effect of allocating twice as much space as
is actually needed to accomodate the genome. The genome of the creature
is 36 instructions long, but it allocates a space of 72 instructions.
This occurred in an environment where the slice size was set equal to the
size of the cell. In this way the creatures were able to garner twice as
much energy. However, they had to compliment this change by doubling the
number of decrements in the loop.
\newpage
\begin{verbatim}
nop_1 ; 01 47 copy loop template COPY LOOP OF 80AAA
nop_0 ; 00 48 copy loop template
nop_1 ; 01 49 copy loop template
nop_0 ; 00 50 copy loop template
mov_iab ; 1a 51 move contents of [bx] to [ax] (copy instruction)
dec_c ; 0a 52 decrement cx
if_cz ; 05 53 if cx = 0 perform next instruction, otherwise skip it
jmp ; 14 54 jump to template below (copy procedure exit)
nop_0 ; 00 55 copy procedure exit compliment
nop_1 ; 01 56 copy procedure exit compliment
nop_0 ; 00 57 copy procedure exit compliment
nop_0 ; 00 58 copy procedure exit compliment
inc_a ; 08 59 increment ax (point to next instruction of daughter)
inc_b ; 09 60 increment bx (point to next instruction of mother)
jmp ; 14 61 jump to template below (copy loop)
nop_0 ; 00 62 copy loop compliment
nop_1 ; 01 63 copy loop compliment
nop_0 ; 00 64 copy loop compliment
nop_1 ; 01 65 copy loop compliment (10 instructions executed per loop)
shl ; 000 03 12 shift left cx COPY LOOP OF 72ETQ
mal ; 000 1e 13 allocate daughter cell
nop_0 ; 000 00 14 top of loop
mov_iab ; 000 1a 15 copy instruction
dec_c ; 000 0a 16 decrement cx
dec_c ; 000 0a 17 decrement cx
jmpb ; 000 15 18 junk
dec_c ; 000 0a 19 decrement cx
inc_a ; 000 08 20 increment ax
inc_b ; 000 09 21 increment bx
mov_iab ; 000 1a 22 copy instruction
dec_c ; 000 0a 23 decrement cx
inc_a ; 000 08 24 increment ax
inc_b ; 000 09 25 increment bx
mov_iab ; 000 1a 26 copy instruction
dec_c ; 000 0a 27 decrement cx
or1 ; 000 02 28 flip low order bit of cx
if_cz ; 000 05 29 if cx == 0 do next instruction
ret ; 000 17 30 exit loop
inc_a ; 000 08 31 increment ax
inc_b ; 000 09 32 increment bx
jmpb ; 000 15 33 go to top of loop (6 instructions per copy)
nop_1 ; 000 01 34 bottom of loop (18 instructions executed per loop)
\end{verbatim}
\end{document}
